package de.jadehs.cosima.converters;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.emf.ecore.util.EcoreUtil;
import org.jgrapht.DirectedGraph;

import de.jadehs.cosima.CosimaFactory;
import de.jadehs.cosima.CosimaUtil;
import de.jadehs.cosima.IConverter;
import de.jadehs.cosima.MultiState;
import de.jadehs.cosima.ReadFromTape;
import de.jadehs.cosima.State;
import de.jadehs.cosima.StateType;
import de.jadehs.cosima.StatesRegister;
import de.jadehs.cosima.Transition;
import de.jadehs.cosima.TransitionsTable;

public class EpsNFAToNFAConverter implements
		IConverter<TransitionsTable, TransitionsTable> {
	public static final EpsNFAToNFAConverter INSTANCE = new EpsNFAToNFAConverter();

	public TransitionsTable convert(TransitionsTable f) {
		if (!CosimaUtil.isEpsNFA(f)) {
			return f;
		}

		State start = CosimaUtil.getStartState(f.getStates());
		DirectedGraph<State, Transition> graph = TransitionsTableToDirectedGraphConverter.INSTANCE
				.convert(f);

		/**
		 * construct a new machine M', see
		 * http://www.csee.umbc.edu/~squire/cs451_l5.html
		 */
		TransitionsTable table = CosimaFactory.eINSTANCE
				.createTransitionsTable();
		{
			table.setTape(EcoreUtil.copy(f.getTape()));
			table.setName(f.getName());
		}

		/**
		 * determine the states of the new machine M' which is the epsilon
		 * closure of each state of the initial machine M
		 */
		Map<State, MultiState> newStates = null;
		{
			StatesRegister reg = CosimaFactory.eINSTANCE.createStatesRegister();
			newStates = createEpsilonClosures(graph, start);
			reg.getStates().addAll(newStates.values());
			table.setStates(reg);
		}

		/**
		 * create new transitions
		 */
		List<Transition> newTransitions = new ArrayList<Transition>(f
				.getTransitions().size());
		{
			List<Character> alphabet = CosimaUtil
					.determineConcreteAlphabet(table);
			// epsilon can/must be ignored
			alphabet.remove(CosimaUtil.EPSILON);

			for (Map.Entry<State, MultiState> e : newStates.entrySet()) {
				MultiState ms = e.getValue();

				for (State s : ms.getStates()) {
					Set<Transition> transitions = graph.outgoingEdgesOf(s);

					for (Transition t : transitions) {
						for (Character c : alphabet) {
							if (CosimaUtil.evaluateStartCondition(t,
									c.charValue())) {
								Transition newTransition = CosimaFactory.eINSTANCE
										.createTransition();
								newTransition.setStart(ms);
								newTransition.setEnd(newStates.get(s));
								ReadFromTape read = CosimaFactory.eINSTANCE
										.createReadFromTape();
								read.setSymbol(c.charValue());
								newTransition.getStartInstructions().add(read);

								newTransitions.add(newTransition);
							}
						}
					}
				}
			}

			table.getTransitions().addAll(newTransitions);
		}

		return table;
	}

	private Map<State, MultiState> createEpsilonClosures(
			DirectedGraph<State, Transition> graph, State start) {
		Map<State, MultiState> ret = new HashMap<State, MultiState>();

		for (State current : graph.vertexSet()) {
			MultiState newState = CosimaFactory.eINSTANCE.createMultiState();
			newState.getStates().add(current);
			createEpsilonClosure(graph, current, newState);
			newState.setName(CosimaUtil.createConcatName(newState.getStates()));
			newState.setStart(current.isStart());
			if (current.getType() == StateType.END) {
				newState.setType(StateType.END);
			}
			ret.put(current, newState);
		}

		return ret;
	}

	public static void createEpsilonClosure(DirectedGraph<State, Transition> graph,
			State current, MultiState newState) {
		Set<Transition> edges = graph.outgoingEdgesOf(current);

		for (Transition t : edges) {
			boolean canEnter = CosimaUtil.evaluateStartCondition(t,
					CosimaUtil.EPSILON);

			if (canEnter) {
				if (!newState.getStates().contains(t.getEnd())) {
					newState.getStates().add(t.getEnd());

					if (t.getEnd().getType() == StateType.END) {
						newState.setType(StateType.END);
					}

					createEpsilonClosure(graph, t.getEnd(), newState);
				}
			}
		}
	}
}
